\documentclass{beamer}

%Comentar a linha acima e descomentar as 3 linhas abaixo para gerar 4 slides por página do PDF.
%\documentclass[handout]{beamer}
%\usepackage{pgfpages}
%\pgfpagesuselayout{4 on 1}[a4paper, border shrink=5mm]

\usepackage[utf8]{inputenc}
\usepackage[portuguese,brazil]{babel}
\usepackage[T1]{fontenc}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{algorithm2e}

\usepackage{color}
\definecolor{Red}{rgb}{1.0, 0.0, 0.0}

\usepackage{url}

\usetheme[secheader]{Madrid}

\author[]{Bruno Caricchio Buss\\Gabriel Guimarães Mendonça\\
Marcelo Rocha Machado\\Ulysses Cardoso Vilela}
\institute[COS886/EEL857 2011.1 - UFRJ]{Universidade Federal do Rio de Janeiro}
\title[DCJ]{Double Cut and Join}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}
  \frametitle{Agenda}
  \tableofcontents
\end{frame}

\section{Introdução}

\subsection{Modelo DCJ}

\begin{frame}

\begin{itemize}
\item Como o nome diz, realiza dois cortes no genoma.
\pause

\vfill

\item Com isso, temos 2 pontas e precisamos fazer uma colagem delas.
\pause

\vfill

\item Consegue reproduzir todas as outras operações de rearranjo.
\end{itemize}

\end{frame}

\subsection{Operações no DCJ}

\begin{frame}

As operações de DCJ terão esta aparência:

\vfill

\pause

\begin{itemize}
    \item $x$ e $y$ são cortes entre 2 genes, neste caso iremos teremos:
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_caso1}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

As operações de DCJ terão esta aparência:

\vfill

\begin{itemize}
    \item $x$ é um corte entre 2 genes e $y$ é um corte no extremo de um cromossomo (um telomero), neste caso teremos:
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_caso2}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

As operações de DCJ terão esta aparência:

\vfill

\begin{itemize}
    \item $x$ e $y$ são cortes no extremo de cromossomos (ou seja, telomeros), neste caso teremos:
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_caso3}
        \end{figure}
\end{itemize}
\end{frame}


\subsection{Modelo Restrito}


\begin{frame}

Porém o modelo DCJ puro tem um problema: \pause Pode-se criar muitas componentes
 circulares no genoma.

\vfill

\pause
A questão é que este tipo de rearranjo não é esperado.

\vfill

\pause
Então o modelo restrito, diz que um genoma só pode ter no máximo uma componente circular no genoma.

\vfill

\pause
Ou seja, se em algum momento uma for criada, ela deve ser:
\begin{itemize}
\item Reintegrada em outra comp. linear.
\item Linearizada.
\end{itemize}

\end{frame}


\subsection{Simulando outras operações}

\begin{frame}

Como dissemos anteriormente, com o DCJ podemos realizar todas as outras operações conhecidas:

\vfill

\pause

\begin{itemize}
    \item Reversão (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_reversao}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

Como dissemos anteriormente, com o DCJ podemos realizar todas as outras operações conhecidas:

\vfill

\begin{itemize}
    \item Translocação (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_transloc}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

Como dissemos anteriormente, com o DCJ podemos realizar todas as outras operações conhecidas:

\vfill

\begin{itemize}
    \item Transposição (2 passos):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_transp}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

Como dissemos anteriormente, com o DCJ podemos realizar todas as outras operações conhecidas:

\vfill

\begin{itemize}
    \item Block Interchange (2 passos):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_blocki}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

Como dissemos anteriormente, com o DCJ podemos realizar todas as outras operações conhecidas:

\vfill

\begin{itemize}
    \item Fusão (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_fusao}
        \end{figure}
\end{itemize}
\end{frame}

\begin{frame}

Como dissemos anteriormente, com o DCJ podemos realizar todas as outras operações conhecidas:

\vfill

\begin{itemize}
    \item Fissão (1 passo):
        \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.8]{dcj_fissao}
        \end{figure}
\end{itemize}
\end{frame}


\section{O Algoritmo}

\subsection{O Grafo de Adjacências}

\begin{frame}

Inicialmente, construímos o \emph{grafo de adjacências} ou \emph{GA} dos genomas $A$ e $B$.

\pause

Exemplo:

\begin{center}
Genoma A: $\overleftarrow{1} \overrightarrow{3} | \overrightarrow{4} \overrightarrow{6} | \overleftarrow{5} \overrightarrow{2}$

Genoma B: $\overrightarrow{1} \overrightarrow{2} \overrightarrow{3} | \overrightarrow{4} \overrightarrow{5} \overrightarrow{6}$
\end{center}

\begin{figure}[htb]
    \centering
    \includegraphics[scale=0.35]{dcj_alg_exemplo_ga}
\end{figure}

\end{frame}

\subsection{Procedimento Guloso}

\begin{frame}

Para cada adjacência de $B$:
\begin{itemize}

\vfill

\item Se esta adjacência já existe em $A$, então não faz nada.

\vfill

\item Caso contrário, encontramos os dois vértices em $A$ correspondentes aos elementos da adjacência em $B$ e operamos para transformar essa adjacência.

\end{itemize}

\end{frame}

\begin{frame}

Para cada telomero de $B$:
\begin{itemize}

\vfill

\item Se esta telomero já existe em $A$, então não faz nada.

\vfill

\item Caso contrário, a adjacência que contem o nosso telomero em $A$ e realizamos uma fissão.

\end{itemize}

\end{frame}

\begin{frame}
Pseudo código:

\begin{algorithm}[H]
Cria o grafo de adjacências\;

\Para{cada adjacência $\{p, q\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;
	$v$ = adjacência em $A$ que contém $q$\;

	\Se{$u \neq v$}{
		$u = \{p, q\}$\;
		$v = \{(u \backslash \{p\}), (v \backslash \{q\})\}$\;
	}
}

\Para{cada telomero $\{-, p\}$ ou $\{p, -\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;

	\Se{u for uma adjacência}{
		$u = \{-, p\}$ ou $\{p, -\}$\;
		Crie um novo nó com $\{-, (u \backslash \{p\})\}$\;
	}
}
\end{algorithm}

\end{frame}


\begin{frame}
Pseudo código, para o modelo restrito:

\begin{algorithm}[H]

Cria o grafo de adjacências\;

\Para{cada adjacência $\{p, q\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;
	$v$ = adjacência em $A$ que contém $q$\;

	\Se{$u \neq v$}{
		$u = \{p, q\}$\;
		$v = \{(u \backslash \{p\}), (v \backslash \{q\})\}$\;
	}

	{\color{Red} Verifica se existe componente circular em $A$, caso sim desfaça}\;
}

\Para{cada telomero $\{-, p\}$ ou $\{p, -\}$ em $B$}{

	$u$ = adjacência em $A$ que contém $p$\;

	\Se{u for uma adjacência}{
		$u = \{-, p\}$ ou $\{p, -\}$\;
		Crie um novo nó com $\{-, (u \backslash \{p\})\}$\;
	}
}
\end{algorithm}

\end{frame}

\subsection{Corretude}

\begin{frame}

\begin{block}{Lema}
Uma operação de \emph{DCJ} altera o número de componentes, lineares e circulares, em no máximo 1.
\end{block}

\pause

\vfill

\begin{block}{Lema}
Uma operação de \emph{DCJ} altera o número de ciclos ímpares no grafo de adjacências em -2, 0 ou +2.
\end{block}

\end{frame}

\begin{frame}

\begin{block}{Lema}
Sejam $A$ e $B$ dois genomas com o mesmo conjunto de $N$ genes cada, então:
\[ A = B \Leftrightarrow N = C + \frac{I}{2}  \]
onde $C$ é o número de ciclos e $I$ é o número de caminhos de tamanho ímpares no grafo de adjacências de $A$ e $B$.
\end{block}

\vfill

\begin{block}{Lema}
Sejam $A$ e $B$ dois genomas com o mesmo conjunto de $N$ genes cada, então:
\[ d_{DCJ}(A, B) \geq N - (C + \frac{I}{2})  \]
onde $C$ é o número de ciclos e $I$ é o número de caminhos de tamanho ímpares no grafo de adjacências de $A$ e $B$.
\end{block}

\end{frame}

\begin{frame}

\begin{block}{Teorema}
Sejam $A$ e $B$ dois genomas com o mesmo conjunto de $N$ genes cada, então:
\[ d_{DCJ}(A, B) = N - (C + \frac{I}{2})  \]
onde $C$ é o número de ciclos e $I$ é o número de caminhos de tamanho ímpares no grafo de adjacências de $A$ e $B$.
\end{block}

\end{frame}

\subsection{Complexidade}

\begin{frame}

\begin{itemize}
 \item Construir o grafo de adjacência: $O(n)$.
 \item Percorrer as adjacências de $B$: $O(n)$.
 \begin{itemize}
	\item Verificar se esta está ok em $A$: $O(1)$.
	\item Corrigir se necessário: $O(1)$.
	\uncover<2>{\item {\color{Red} Detectar ciclos e corrigir: $O(n)$}}
 \end{itemize}
 \item Percorrer os telomeros de $B$: $O(n)$.
 \begin{itemize}
	\item Verificar se esta está ok em $A$: $O(1)$.
	\item Corrigir se necessário: $O(1)$.
 \end{itemize}
\end{itemize}

Complexidade total: \alt<1>{$O(n)$}{{\color{Red}$O(n^2)$}}

\end{frame}

\section{Implementação}

\begin{frame}[fragile]

Detalhes da implementação:

\begin{itemize}

\pause
\item Algoritmo implementado em  C
\vfill
\pause
\item Gerador de entradas implementado em Perl
\vfill
\pause
\item O grafo de adjacência é construído e utilizado de forma implícita, utilizando apenas
	   tabelas.

\vfill
\pause
\item Formato de input:
\begin{center}
\begin{verbatim}
11
+1 -2 -3 +4 +9 -8 +7 | +10 -5 -6 | +11
+1 +2 +3 | +4 +5 +6 | +7 +8 +9 +10 +11
\end{verbatim}
\end{center}
\vfill
\pause
\item Estruturas de dados utilizadas.
\vfill
\pause
\item Argumentos via linha de comando.
\end{itemize}


\end{frame}

\section*{Dúvidas?!}

\begin{frame}
 \begin{center}
  Dúvidas ?
 \end{center}
\end{frame}

\begin{frame}
 \begin{center}
  Obrigado!

\vfill

\url{code.google.com/p/cos886-dcj/}
 \end{center}
\end{frame}

\end{document}
​
